import java.util.Arrays;

public class Test_2 {
    //建小堆(建大堆类似)
    public static void shiftDown(int[] arr,int index) {
        int parent = index;
        int child = 2 * parent + 1;
        while (child < arr.length) {
            if (child + 1 < arr.length && arr[child + 1] < arr[child]) {
                child = child + 1;
            }
            if (arr[child] < arr[parent]) {
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
                parent = child;
                child = 2 * child + 1;
            } else {
                //调整完毕，退出了
                break;
            }

        }

    }
    public static void creadHeap(int[] arr) {
        int lastParent = arr.length - 1;
        int lastleaf = (lastParent - 1) / 2;
        for(int i = lastleaf;i >= 0;i--) {
            shiftDown(arr,i); 
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,4,10,5,8,1,16};
        creadHeap(arr);
        System.out.println(Arrays.toString(arr));
    }

}
